home *** CD-ROM | disk | FTP | other *** search
/ Celestin Apprentice 5 / Apprentice-Release5.iso / Source Code / C / Games / Arashi 1.1.1 / source code / For your think c folder / Classes / CStringDictionary.c < prev    next >
Encoding:
C/C++ Source or Header  |  1995-06-01  |  7.1 KB  |  334 lines  |  [TEXT/KAHL]
  1. /*/
  2.      Project Arashi: CStringDictionary.c
  3.      Major release: Version 1.1d2, 9/5/95
  4.  
  5.      Last modification: Thursday, June 1, 1995, 1:23
  6.      Created: Friday, December 4, 1992, 11:45
  7.  
  8.      Copyright © 1992-1995, Juri Munkki
  9. /*/
  10.  
  11. /*
  12. **    See include file for more details on how this class works.
  13. */
  14. #include "CStringDictionary.h"
  15. #include <RamFiles.h>
  16.  
  17. /*
  18. **    Given a counted string of length len, HashString
  19. **    will return a value from 0 to HASHTABLESIZE-1.
  20. **    This value can be used as the hashing value for
  21. **    that string.
  22. */ 
  23. short    HashString(
  24.     unsigned char     *string,
  25.     short            len)
  26. {    
  27.     if(len>0)
  28.     {    return (string[0]+string[len-1]+string[len>>1]) & (HASHTABLESIZE - 1);
  29.     }
  30.     else
  31.         return 0;
  32. }
  33. /*
  34. **    Initialize a CStringDictionary. The directory will be empty.
  35. */
  36. void    CStringDictionary::IStringDictionary()
  37. {
  38.     int        i;
  39.     
  40.     dictCount = 0;                    //    Dictionary is empty.
  41.     logicalDictSize = 0;
  42.     realDictSize = 0;
  43.     dictionary = (DictEntry **)NewHandle(0);
  44.     
  45.     logicalWordListSize = 0;        //    Dictionary words are listed separately.
  46.     realWordListSize = 0;
  47.     wordList = (unsigned char **)NewHandle(0);
  48.         
  49.     for(i=0;i<HASHTABLESIZE;i++)    //    Hash table is empty.
  50.     {    hashTable[i] = -1;
  51.     }
  52.  
  53.     IBaseObject();
  54. }
  55.  
  56. /*
  57. **    Return count of items in dictionary.
  58. */
  59. short    CStringDictionary::GetDictionarySize()
  60. {
  61.     return dictCount;
  62. }
  63.  
  64. /*
  65. **    Copy the string for entry index to theEntry
  66. */
  67. void    CStringDictionary::GetIndEntry(
  68.     short        index,
  69.     StringPtr    theEntry)
  70. {
  71.     DictEntry    *thisEntry;
  72.     StringPtr    entryString;
  73.     short        i;
  74.     
  75.     if(index >= 0 && index < dictCount)
  76.     {
  77.         thisEntry = index + (DictEntry *) *dictionary;
  78.         entryString = thisEntry->nameOffset + *wordList;
  79.         
  80.         i = 1+entryString[0];
  81.         while(i--)
  82.         {    theEntry[i] = entryString[i]; 
  83.         }
  84.     }
  85. }
  86.  
  87. short    CStringDictionary::GetIndEntrySize(
  88.     short    index)
  89. {
  90.     DictEntry    *thisEntry;
  91.     StringPtr    entryString;
  92.     short        i;
  93.     
  94.     if(index >= 0 && index < dictCount)
  95.     {
  96.         thisEntry = index + (DictEntry *) *dictionary;
  97.         entryString = thisEntry->nameOffset + *wordList;
  98.         
  99.         return entryString[0];
  100.     }
  101.     else
  102.         return    0;
  103. }
  104.  
  105. /*
  106. **    Add a dictionary entry regardless
  107. **    of wether it already is there or not. Normally you would
  108. **    first look for a dictionary entry before calling this
  109. **    routine. Call this routine if you are absolutely sure
  110. **    that the entry isn't already in the dictionary.
  111. **
  112. **    NOTE: A negative return value signifies and error.
  113. */
  114. tokentype    CStringDictionary::AddDictEntry(
  115.     unsigned char    *entry,
  116.     short            len)
  117. {
  118.     long            where;
  119.     tokentype        entryIndex = 0;
  120.     long            theErr = noErr;
  121.     short            hashed;
  122.     SignedByte        state;
  123.     DictEntry        *entryP;
  124.     
  125.     if(len<0) len = *entry;
  126.     if(len>255) len = 255;
  127.  
  128.     state = HGetState((Handle) this);    //    Lock the object for a while.
  129.     HLock((Handle)this);
  130.     
  131.     //    Increase the dictionary size, if memory allows.
  132.     if(IncreaseByClump(    (Handle)dictionary,
  133.                         &realDictSize,
  134.                         &logicalDictSize,
  135.                         sizeof(DictEntry),
  136.                         DICTIONARYCLUMPSIZE) == noErr)
  137.     {
  138.         where = logicalWordListSize;    //    New word is written at this offset.
  139.         
  140.         //    Increase the word list size, if memory allows.
  141.         if(IncreaseByClump(    (Handle)wordList,
  142.                             &realWordListSize,
  143.                             &logicalWordListSize,
  144.                             len+1,
  145.                             WORDCLUMPSIZE) == noErr)
  146.         {    BlockMoveData(entry+1,1+where+*wordList,len);    //    Write the word.
  147.             (*wordList)[where] = len;                    //    Store the length
  148.             entryIndex = dictCount++;                    //    Get a new token value (or index).
  149.             entryP = entryIndex + *dictionary;            //    A pointer to the entry.
  150.             
  151.             hashed = HashString(entry+1,len);            //    Hash the entry by adding it
  152.             entryP->hashLink = hashTable[hashed];        //    in front of all other entries
  153.             entryP->nameOffset = where;                    //    in the linked list of words
  154.             hashTable[hashed] = entryIndex;                //    hashing to the same entry.
  155.         }
  156.         else
  157.         {    logicalDictSize -= sizeof(DictEntry);        //    Memory was full or handle locked.
  158.             theErr = memFullErr;                        //    Assume that memory was full...
  159.         }
  160.     }
  161.     else
  162.     {    theErr = memFullErr;                            //    Memory was full or handle locked.
  163.     }
  164.  
  165.     HSetState((Handle)this,state);            //    Restore the object lock state.
  166.     return theErr ? theErr : entryIndex;    //    Return an error or the entry.
  167. }
  168.  
  169. /*
  170. **    Look for an entry and return it if found. Return
  171. **    -1 if the entry is not found.
  172. */
  173. tokentype    CStringDictionary::SearchForEntry(
  174.     unsigned char    *entry,
  175.     short            len)
  176. {
  177.     short            hashWalk;
  178.     DictEntry        *thisEntry;
  179.     unsigned char    *p1,*p2;
  180.     
  181.     if(len<0) len = *entry;
  182.     if(len>255) len = 255;
  183.     
  184.     hashWalk = hashTable[HashString(entry+1,len)];    //    Find linked list head.
  185.     while(hashWalk >= 0)                            //    While there are items in the list.
  186.     {    p1 = entry+1;
  187.         thisEntry = hashWalk + *dictionary;
  188.         p2 = thisEntry->nameOffset + *wordList;        //    Compare the entries:
  189.         
  190.         if(len == *p2++)                            //    Compare length.
  191.         {    int    i;
  192.         
  193.             i = len;
  194.             while((i > 0) & (*p1++ == *p2++))        //    Compare characters.
  195.                 i--;
  196.         
  197.             if(i == 0)
  198.                 return hashWalk;                    //    Found! Return index.
  199.             else
  200.                 hashWalk = thisEntry->hashLink;        //    Not found, look at next entry.
  201.         }
  202.         else
  203.         {    hashWalk = thisEntry->hashLink;            //    Not found, look at next entry.
  204.         }
  205.     }
  206.  
  207.     return -1;        //    Return -1 when entry was not found.
  208. }
  209.  
  210. /*
  211. **    Look for an entry and if doesn't exist, create it.
  212. **    This routine only returns an error if there is a
  213. **    problem with memory management.
  214. */
  215. tokentype    CStringDictionary::FindEntry(
  216.     unsigned char     *entry,
  217.     short            len)
  218. {
  219.     tokentype    theToken;
  220.     
  221.     theToken = SearchForEntry(entry,len);
  222.     if (theToken >= 0) 
  223.         return theToken;
  224.     else
  225.         return AddDictEntry(entry,len);
  226. }
  227.  
  228. /*
  229. **    Unlock and dispose storage.
  230. */
  231. void    CStringDictionary::Dispose()
  232. {
  233.     ForceUnlock();
  234.     DisposHandle((Handle)wordList);
  235.     DisposHandle((Handle)dictionary);
  236.  
  237.     inherited::Dispose();
  238. }
  239.  
  240. /*
  241. **    Lock everything.
  242. */
  243. void    CStringDictionary::Lock()
  244. {
  245.     if(!lockCounter)
  246.     {    HLock((Handle)wordList);
  247.         HLock((Handle)dictionary);
  248.     }
  249.     inherited::Lock();
  250.  
  251. }
  252. /*
  253. **    Unlock everything.
  254. */
  255. void    CStringDictionary::Unlock()
  256. {
  257.     if(lockCounter == 1)
  258.     {    HUnlock((Handle)wordList);
  259.         HUnlock((Handle)dictionary);
  260.     }
  261.     inherited::Unlock();
  262. }
  263.  
  264. /*
  265. **    Read the dictionary string from a STR# resource.
  266. */
  267. void    CStringDictionary::ReadFromStringList(
  268.     short strListID)
  269. {
  270.     Str255    theString;
  271.     short    stringCount,i;
  272.     
  273.     stringCount = **(short **)GetResource('STR#',strListID);
  274.     for(i=1;i<=stringCount;i++)
  275.     {    GetIndString(theString,strListID,i);
  276.         AddDictEntry(theString, *theString);
  277.     }
  278. }
  279.  
  280. Handle    CStringDictionary::WriteToHandle()
  281. {
  282.     Handle    result;
  283.     long    neededSize;
  284.     short    ind;
  285.     short    stringCount;
  286.     
  287.     stringCount = GetDictionarySize();
  288.     neededSize = sizeof(stringCount);
  289.     
  290.     for(ind = 0; ind < stringCount; ind++)
  291.     {    neededSize += 1+GetIndEntrySize(ind);
  292.     }
  293.  
  294.     result = NewHandle(neededSize);
  295.     if(result)
  296.     {    unsigned char    *p;
  297.         
  298.         
  299.         HLock(result);
  300.         p = sizeof(stringCount) + (unsigned char *)*result;
  301.         for(ind = 0;ind < stringCount; ind++)
  302.         {    GetIndEntry(ind, (StringPtr)p);
  303.             p += 1+p[0];
  304.         }
  305.         HUnlock(result);
  306.     }
  307.     
  308.     return result;
  309. }
  310.  
  311. void    CStringDictionary::ReadFromHandle(
  312.     Handle    source)
  313. {
  314.     short    ind;
  315.     short    stringCount;
  316.     char    cMemTags;
  317.     
  318.     if(source)
  319.     {    unsigned char    *p;
  320.     
  321.         cMemTags = HGetState(source);
  322.         HLock(source);
  323.         p = (unsigned char *) *source;
  324.         
  325.         stringCount = *(short *) p;
  326.         p += sizeof(short);
  327.         for(ind = 0;ind < stringCount; ind++)
  328.         {    AddDictEntry(p, -1);
  329.             p += 1+p[0];
  330.         }
  331.         
  332.         HSetState(source, cMemTags);
  333.     }
  334. }